package practice.linkedlist;

import java.util.Stack;

public class SingleLinkedListPractice01 {
    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.add(new Node(1, "节点1"));
        singleLinkedList.add(new Node(2, "节点2"));
        singleLinkedList.add(new Node(3, "节点3"));
        singleLinkedList.add(new Node(4, "节点4"));
        singleLinkedList.add(new Node(5, "节点5"));

        //求单链表中有效节点的个数
        //System.out.println(length(singleLinkedList.getHead()));

        //查找单链表中倒数第k个节点（新浪）
//        Node lastIndexNode = findLastIndexNode(singleLinkedList.getHead(), 1);
//        System.out.println("倒数第k个节点 = " + lastIndexNode);

/*
        System.out.println("======== 反转前 =======");
        singleLinkedList.list();

        //单链表反转
        reverse(singleLinkedList.getHead());
        System.out.println("======== 反转后 =======");
        singleLinkedList.list();
*/

        reversePrint(singleLinkedList.getHead());


    }

    //求单链表中有效节点的个数
    public static int length(Node node){
        //空链表
        if (node.next == null){
            return 0;
        }
        int length = 0;
        //遍历链表
        while (node.next != null){
            length++;
            node = node.next;
        }
        return length;

    }

    /**
     * 查找单链表中倒数第k个节点（新浪）
     * 分析
     * 1. 编写一个方法，接收head节点，同时接收一个index
     * 2. index表示倒数的第index节点
     * 3. 先把链表从头到尾遍历，得到整个链表的长度size
     * 4. 得到size后，再遍历一次，这次只遍历到(size - index)个就可以得到
     * @param node
     * @param index
     * @return
     */
    public static Node findLastIndexNode(Node node, int index){
        if (node.next == null){
            System.out.println("链表为空");
            return null;
        }
        int size = length(node);
        if (index > size || index <= 0){
            System.out.println("index超出链表长度范围，无法获取！");
            return null;
        }
        //遍历链表
        Node temp = node.next;
        for (int i = 0; i < (size - index); i++) {

            //指针后移
            temp = temp.next;
        }
        //返回找到的节点
        return temp;
    }

    /**
     * 单链表的反转（腾讯）
     * @param head
     */
    public static void reverse(Node head){
        //没有节点和只有一个节点的情况
        if (head.next == null || head.next.next == null){
            return;
        }

        Node temp = head.next;
        //创建一个新的节点
        Node newNodeHead = new Node(0, null);
        Node newNodeTemp = null;
        //originNodeNext保存原链表遍历出来的当前节点之后的链表内容
        Node originNodeNext = null;
        //遍历链表
        while (temp != null){
            //temp为遍历出来的节点，用一个临时节点指向它
            newNodeTemp = temp;
            //originNodeNext保存原链表遍历出来的当前节点之后的链表内容
            //这里必须存在当前节点之后的链表内容，否则链表内容（temp）改变之后无法继续往下遍历
            originNodeNext = temp.next;
            //将遍历出来的节点newNodeTemp（temp）指向 新节点的头节点下的next
            newNodeTemp.next = newNodeHead.next;
            //新节点的头节点下的next 指回 保存的遍历处理的节点的遍历newNodeTemp
            newNodeHead.next = newNodeTemp;

            //指针后移：originNodeNext保存着原链表遍历出来的当前节点之后的链表内容
            temp = originNodeNext;
        }
        //让原链表的头节点 指向 新链表头节点的next
        head.next = newNodeHead.next;

    }

    /**
     * 从尾到头打印单链表（百度）
     * @param head
     */
    public static void reversePrint(Node head){
        if (head.next == null){
            return;
        }

        Node temp = head.next;
        Stack<Node> stack = new Stack<>();

        while (temp != null){
            stack.push(temp);
            temp = temp.next;
        }
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }

}
